package 题目集.图.最短路;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode.cn/problems/minimum-cost-to-reach-destination-in-time/description/?envType=daily-question&envId=2024-10-03
 */
public class z_demo03_error {
    /**
     * 暴力解：
     * dfs遍历所有能到达的路径，从选个符合条件且最小的。
     */
    static int maxn = 1010;
    static int maxTime = 1010;
    List<int[]>[] graph = new List[maxn];
    int[] passingFees;
    int n;
    boolean[] vis = new boolean[maxn];


    /**
     * dp错误思路：下面的dp是漏掉了vis数组
     * @return
     */
    public int minCost(int maxTime, int[][] edges, int[] passingFees) {
        for (int i = 0; i < graph.length; i++) {
            graph[i] = new ArrayList<>();
        }
        this.passingFees = passingFees;
        n = passingFees.length;
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            int t = edge[2];
            graph[u].add(new int[]{v, t});
            graph[v].add(new int[]{u, t});
        }
        int res = dfs(0, maxTime);
        return res == Integer.MAX_VALUE ? -1 : res;
    }

    int[][] dp = new int[maxn][maxTime];

    /**
     * dp错误思路：这里的dp是漏掉了vis数组，不是这样dp的，然而那种方式我想不出来
     * @param cur
     * @param restTime
     * @return
     */
    public int dfs(int cur, int restTime) {
        if (dp[cur][restTime] != 0) return dp[cur][restTime];
        if (cur == n - 1) return passingFees[cur];
        vis[cur] = true;
//        restTime -= passingFees[cur];
        /*下一个点所需的花费*/
        int result = Integer.MAX_VALUE;
        for (int[] edge : graph[cur]) {
            int to = edge[0];
            int cost = edge[1];
            if (!vis[to] && restTime >= cost) {
                int time = dfs(to, restTime - cost);
                result = Math.min(time, result);
            }
        }
        vis[cur] = false;
        dp[cur][restTime] = result == Integer.MAX_VALUE ? Integer.MAX_VALUE : passingFees[cur] + result;
        return dp[cur][restTime];
    }

    @Test
    public void client1() {
        int maxTime = 30;
//        minCost();
    }

}
